package algorithms.leecode;

import java.util.HashSet;
import java.util.Set;

/**
 * 这题居然是中等题，麻了
 */
public class Au81 {
    public boolean search(int[] nums, int target) {
        if (nums.length == 0) {
            return false;
        }
        int start = 0;
        int end = nums.length - 1;
        if (end == 0) {
            if (target == nums[end]) {
                return true;
            }
            return false;
        }
       while (start <= end) {
           int mid = start + (end - start) / 2;
           if (nums[mid] == target) {
               return true;
           }else
           if (nums[start] == nums[mid] && nums[mid] == nums[end]) {
               start++;
               end--;
               // 有序数组上
           }  else if (nums[start] <= nums[mid]) {
               if (target < nums[mid] && nums[start] <= target) {
                   end = mid - 1;
               } else {
                   start = mid + 1;
               }
           } else {
              if (target > nums[mid] && target <= nums[end]) {
                   start = start + 1;
               } else {
                  end = mid - 1;
              }
           }
       }

        return false;
    }

    public static void main(String[] args) {

        int[] nums = {3,1};
        System.err.println(new Au81().search(nums,1));

    }
}
